package com.dyz.leetcode._14_binarySearchTree;

import com.dyz.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class _98_isValidBST {
    public boolean isValidBST(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);

        for(int i=1; i<res.size(); i++){
            if(res.get(i)<=res.get(i-1)){return false;}
        }
        return true;

    }

    private void inorder(TreeNode node, List<Integer> res){
        if(node==null){return;}

        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }

    // 2. 中序遍历 (边遍历边验证顺序性)
    private TreeNode prev = null;
    private boolean isBST = true;
    public boolean isValidBST1(TreeNode root) {

        inorder1(root);

        return isBST;
    }

    private void inorder1(TreeNode node) {
        if (node == null) {return;}

        inorder1(node.left);
        if (prev != null && node.val <= prev.val) {
            // 不符合 BST 性质
            isBST = false;
            return;
        }
        prev = node;
        inorder1(node.right);
    }
}
